package leetcode.medium.limit400;

import java.util.PriorityQueue;

public class No378 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1, 5, 9}, {10, 11, 13}, {12, 13, 15}};
        System.out.println(new No378().kthSmallest(matrix, 8));
    }

    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            return o1[0] - o2[0];
        });
        for (int i = 0; i < matrix.length; i++) {
            queue.offer(new int[]{matrix[i][0], i, 0});
        }
        int res = -1;
        while (!queue.isEmpty() && k > 0) {
            int[] curr = queue.poll();
            res = curr[0];
            int i = curr[1];
            int j = curr[2];
            if (j + 1 < matrix.length) {
                queue.offer(new int[]{matrix[i][j + 1], i, j + 1});
            }
            k--;
        }
        return res;
    }
}
